import functools


class Solution(object):
    def canPartitionKSubsets(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        total = sum(nums)
        if total % k != 0:
            return False
        target = total // k
        if max(nums) > target:
            return False
        n = len(nums)

        @functools.cache
        def search(val, t):
            if t == k - 1:
                return True
            index = 0
            while index < n:
                if (val >> index) & 1 == 1:
                    now_count = nums[index]
                    val -= (1 << index)
                    break
                else:
                    index += 1
            if now_count == target:
                return search(val, t + 1)
            now = {val: now_count}
            for i in range(index + 1, n):
                next_dict = {}
                for val in now:
                    now_count = now[val]
                    next_dict[val] = now[val]
                    if (val >> i) & 1 == 1:
                        now_val = val - (1 << i)
                        if now_count + nums[i] == target:
                            if search(now_val, t + 1):
                                return True
                        else:
                            if now_count + nums[i] < target:
                                next_dict[now_val] = now_count + nums[i]
                now = next_dict
            return False

        return search(2 ** n - 1, 0)


data = Solution()
nums = [4, 3, 2, 3, 5, 2, 1]
k = 4
print(data.canPartitionKSubsets(nums, k))
